package com.algorithm.example.queue.queue.priority;

import com.algorithm.example.queue.queue.Queue;

import java.util.Iterator;

/**
 * <p>
 * 基于大顶堆实现优先级队列
 * </p>
 *
 * @author lzt
 * @version 1.0
 * @since 2024/1/27 16:33
 */
public class PriorityQueue3<E extends Priority> implements Queue<E>, Iterable<E> {

    Priority[] array;
    int size;

    public PriorityQueue3(int capacity) {
        this.array = (E[]) new Priority[capacity + 1];
    }

    /**
     * 1.入堆新元素，加入到数组末尾（索引位置chiLd）
     * 2.不断比较新加元工与它父节点（parent）优先级
     * - 如果父节点优先级低，则向下移动，并找到下一个parent
     * - 直至父节点优先级更高或chiLd==θ为止
     */
    @Override
    public boolean offer(E value) {
        if (isFull()) {
            return false;
        }
        int child = size++;
        int parent = (child - 1) / 2;
        while (child > 0 && array[parent].Priority() < value.Priority()) {
            array[child] = array[parent];
            child = parent;
            parent = (child - 1) / 2;
        }
        array[child] = value;
        return true;
    }

    private void swap(int child, int parent) {
        Priority priority = array[child];
        array[child] = array[parent];
        array[parent] = priority;
    }

    /**
     * 下滑
     * 求出左右两子的索引，然后取大的，
     * 赋回给max，进行交换，然后递归重复这个操作
     */
    private void down(int index) {
        int left = 2 * index + 1;
        int right = left + 1;
        int max = index;

        if (left < size && array[left].Priority() > array[max].Priority()) {
            max = left;
        } else if (right < size && array[right].Priority() > array[max].Priority()) {
            max = right;
        }
        if (max != index) {
            swap(max, index);
            down(max);
        }
    }


    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }
        swap(0, size - 1);
        size--;
        Priority priority = array[size];
        array[size] = null;
        // 下滑
        down(0);
        return (E) priority;
    }

    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        return (E) array[0];
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean isFull() {
        return size == array.length;
    }

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            int p = 0;

            @Override
            public boolean hasNext() {
                return p != size;
            }

            @Override
            public E next() {
                Priority priority = array[p];
                p++;
                return (E) priority;
            }
        };
    }
}
